#include <bits/stdc++.h>

using namespace std;

// 串联所有单词的子串
// 给定一个字符串s和一个字符串数组words
// words中所有字符串长度相同
// s中的串联子串是指一个包含 words中所有字符串以任意顺序排列连接起来的子串
// 例如words = { "ab","cd","ef" }
// 那么"abcdef"、"abefcd"、"cdabef"、"cdefab"、"efabcd"、"efcdab"都是串联子串。 
// "acdbef"不是串联子串，因为他不是任何words排列的连接
// 返回所有串联子串在s中的开始索引
// 你可以以任意顺序返回答案
// 测试链接 : https://leetcode.cn/problems/substring-with-concatenation-of-all-words/

class Solution 
{
public:
    using ull = unsigned long long;
    static const int MAXN = 10001;
    static const int base = 499;
    ull p[MAXN], h[MAXN];

    void build(string& str)
    {
        p[0] = 1;
        for(int j = 1; j < MAXN; ++j) p[j] = p[j - 1] * base;
        h[0] = str[0] - 'a' + 1;
        for(int j = 1; j < str.size(); ++j)
        {
            h[j] = h[j - 1] * base + str[j] - 'a' + 1;
        }
    }

    // 范围是s[l,r)，左闭右开
    ull hash(int l, int r)
    {
        ull ans = h[r - 1];
        ans -= l == 0 ? 0 : (h[l - 1] * p[r - l]);
        return ans;
    }

    // 计算一个字符串的哈希值
    ull hash(string& str)
    {
        if(str == "") return 0;
        int n = str.size();
        ull ans = str[0] - 'a' + 1;
        for(int j = 1; j < n; ++j)
        {
            ans = ans * base + str[j] - 'a' + 1;
        }
        return ans;
    }

	// 如果s的长度为n，words里所有单词的总长度为m
	// 时间复杂度O(n + m)，最优解的时间复杂度与单词个数、单词长度是无关的
	// 所有题解都没有做到这个复杂度的
	// 虽然这个做法打败比例没有到100%，但那是因为测试数据量不够大
	// 所以最优解的时间复杂度优势没有体现出来
	// 这个方法绝对是最优解，只有用字符串哈希，时间复杂度才能到最优
    vector<int> findSubstring(string s, vector<string>& words) 
    {
        vector<int> ans;
        // words的词频表
        unordered_map<ull, int> map;
        for(string& key : words)
        {
            ull v = hash(key);
            ++map[v];
        }
        build(s);
        int n = s.size();
        int wordLen = words[0].size();
        int wordNum = words.size();
        int allLen = wordLen * wordNum;
        // 窗口的词频表
        unordered_map<ull, int> window;
        for(int init = 0; init < wordLen && init + allLen <= n; ++init)
        {
            // init是当前组的首个开头
            int debt = wordNum;
            // 建立起窗口
            for(int l = init, r = init + wordLen, part = 0; part < wordNum; l += wordLen, r += wordLen, ++part)
            {
                ull cur = hash(l, r);
                ++window[cur];
                if(window[cur] <= map[cur]) --debt;
            }
            if(debt == 0) ans.push_back(init);
            // 接下来窗口进一个、出一个
            for(int l1 = init, r1 = init + wordLen, l2 = init + allLen,
                    r2 = init + allLen + wordLen; r2 <= n; l1 += wordLen, r1 += wordLen, l2 += wordLen, r2 += wordLen)
            {
                ull out = hash(l1, r1);
                ull in = hash(l2, r2);
                --window[out];
                if(window[out] < map[out]) ++debt;
                ++window[in];
                if(window[in] <= map[in]) --debt;
                if(debt == 0) ans.push_back(r1);
            }
            window.clear();
        }
        return ans;
    }
};


class Solution 
{
public:
    vector<int> findSubstring(string s, vector<string>& words) 
    {
        unordered_map<string, int> cnt1;
        for(auto& word : words) ++cnt1[word];

        int len = words[0].size(), n = s.size(), m = words.size();
        vector<int> ans;
        for(int i = 0; i < len; ++i)
        {
            unordered_map<string, int> cnt2;
            for(int left = i, right = i, cnt = 0; right + len <= n; right += len)
            {
                string in = s.substr(right, len);
                ++cnt2[in];
                if(cnt1.count(in) && cnt2[in] <= cnt1[in]) ++cnt;
                if(right - left + 1 > len * m)
                {
                    string out = s.substr(left, len);
                    if(cnt1.count(out) && cnt2[out] <= cnt1[out]) --cnt;
                    --cnt2[out];
                    left += len;
                }
                if(cnt == m) ans.push_back(left);
            }
        }
        return ans;
    }
};